package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/all-possible-full-binary-trees/">所有可能的真二叉树(All Possible Full Binary Trees)</a>
 * <p>给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。</p>
 * <p>答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。</p>
 * <p>真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。</p>
 * </p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 7
 *      输出：[
 *              [0,0,0,null,null,0,0,null,null,0,0],
 *              [0,0,0,null,null,0,0,0,0],
 *              [0,0,0,0,0,0,0],
 *              [0,0,0,0,0,null,null,null,null,0,0],
 *              [0,0,0,0,0,null,null,0,0]
 *            ]
 *
 * 示例 2：
 *      输入：n = 3
 *      输出：[[0,0,0]]
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= n <= 20</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/17 11:53
 */
public class LC0894AllPossibleFullBinaryTrees_M {

    static class Solution {
        public List<TreeNode> allPossibleFBT(int n) {
            return allPossibleFBT(n, new HashMap<>());
        }

        private List<TreeNode> allPossibleFBT(int n, Map<Integer, List<TreeNode>> map) {
            if (!map.containsKey(n)) {
                List<TreeNode> ans = new ArrayList<>();
                if (n == 1) {
                    ans.add(new TreeNode(0));
                } else if (n % 2 == 1) {
                    // 左子树中节点数为 x；右子树节点数为 y。
                    for (int x = 0; x < n; x++) {
                        // 右子树的节点数为：n - 左子树节点数 - 根节点
                        int y = n - x - 1;
                        for (TreeNode left : allPossibleFBT(x, map)) {
                            for (TreeNode right : allPossibleFBT(y, map)) {
                                TreeNode bns = new TreeNode(0);
                                bns.left = left;
                                bns.right = right;
                                ans.add(bns);
                            }
                        }
                    }
                }
                map.put(n, ans);
            }
            return map.get(n);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (TreeNode node : solution.allPossibleFBT(7)) {
            TreeNode.printTree(node);
            System.out.println("================");
        }
    }
}
